package com.datastructure.test.entirepacket;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class EntirePacket {

    public static void main(String[] args) {
        EntirePacket entirePacket = new EntirePacket();
        ArrayList<ArrayList<Integer>> nums = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(5);
        list1.add(10);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(1);
        nums.add(list1);
        nums.add(list2);
        entirePacket.knapsack(6,2,nums);
    }

    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        // write code here
        int maxFillValue = 0;
        ArrayList<Integer> result = new ArrayList<>(2);
        Good[] data = new Good[n];
        ArrayList<ArrayList<Good>> res = new ArrayList<>();
        LinkedList<Good> linkedList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> list = nums.get(i);
            data[i]=new Good(list.get(0),list.get(1));
        }
        int maxValue = computeMaxValue(v,n,nums);
        computeMaxFillValue(v,data,linkedList,res);
        for (ArrayList<Good> list : res) {
            int temp = 0;
            for (Good good : list) {
                temp+= good.value;
            }
            maxFillValue=Math.max(maxFillValue,temp);
        }
        result.add(maxValue);
        result.add(maxFillValue);
        return result;
    }

    private void computeMaxFillValue(int target, Good[] data,LinkedList<Good> linkedList,ArrayList<ArrayList<Good>> res) {
        if(target<0){
            return;
        }
        if(target==0&&linkedList.size()>0){
            res.add(new ArrayList<>(linkedList));
        }
        for (Good datum : data) {
            linkedList.add(datum);
            computeMaxFillValue(target - datum.volume, data, linkedList, res);
            linkedList.removeLast();
        }
    }

    private int computeMaxValue(int v, int n, ArrayList<ArrayList<Integer>> nums) {
        int[] w = new int[n];
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> list = nums.get(i);
            w[i]= list.get(0);
            val[i]=list.get(1);
        }
        int[][] V = new int[n+1][v+1];
        for (int i = 0; i < V.length; i++) {
            V[i][0]=0;
        }
        Arrays.fill(V[0], 0);
        for (int i = 1; i < V.length; i++) {
            for (int j = 1; j < V[0].length; j++) {
                if(w[i-1]>j){
                    V[i][j]=V[i-1][j];
                } else {
                    V[i][j] = Math.max(V[i - 1][j], val[i - 1] + V[i - 1][j - w[i - 1]]);
                }
            }
        }
        return V[n][v];
    }

    public ArrayList<Integer> knapsack1 (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        ArrayList<Integer> res = new ArrayList<>();
        //问题1
        int[] dp = new int[v+1];
        //问题2
        int[] dp1 = new int[v+1];
        for(int i = 1;i <= v;++i){
            int max = Integer.MIN_VALUE;
            int max1 = Integer.MIN_VALUE;
            for(int j = 0;j < n;++j){
                if(i >= nums.get(j).get(0)){
                    // 遍历所有物品，找出能够装入当前背包的最大价值
                    max = Math.max(dp[i - nums.get(j).get(0)] + nums.get(j).get(1),max);
                    // 问题2要求背包正好装满，故无需去计算不装满背包的情况
                    max1 = Math.max(dp1[i - nums.get(j).get(0)] + nums.get(j).get(1),max1);
                }
                // 背包不装满
                max = Math.max(max,dp[i-1]);
            }
            dp[i] = max;
            dp1[i] = max1;
        }
        res.add(dp[v]);
        res.add(Math.max(dp1[v], 0));
        return res;
    }
}
class Good{
   public int volume;
   public int value;

    public Good(int volume, int value) {
        this.volume = volume;
        this.value = value;
    }
}
